package cn.kent.simple;

/**
 * 67. 二进制求和
 */
public class AddBinary {
    public static void main(String[] args) {
        String s = addBinary("11", "1");// 100
        System.out.println("结果为：" + s);
    }

    /**
     * 先将a、b转成十进制数进行计算，然后转成二进制返回
     * 但是 -> 为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。
     */
    public static String addBinary2(String a, String b) {
        return Integer.toBinaryString(
                Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );
    }

    /**
     * 补零计算
     * 1ms 100%
     * 时间复杂度：O(n) 遍历了一次a和b字符串
     */
    public static String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; i++) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0; // 防止越界 carry表示进位，当carry一次循环后等于2，则表示需要进位
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2; // 下次循环进位让ans.append('1')
        }
        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();
        return ans.toString();
    }
}
